package com.tanzc.sort;

import com.tanzc.util.ArrayUtils;

import java.util.Date;

/**
 * <p> description: 选择排序</p>
 *
 * @author tanzc
 * @date 2021/12/23
 **/
public class SelectionSort {
    public static void main(String[] args) {
        SelectionSort selectionSort = new SelectionSort();
        int num = 20000, max = 10;
        int[] arr = ArrayUtils.random(num, max);
//        int[] arr = ArrayUtils.worst(num);
//        int[] arr = ArrayUtils.bad(num);
//        int[] arr = ArrayUtils.nice(num);

        int[] arr1 = new int[num];
        System.arraycopy(arr, 0, arr1, 0, num);

        System.out.print("选择排序-----time: ");
        Date start = new Date();
        selectionSort.selction(arr1);
        Date end = new Date();
        long timediff = end.getTime() - start.getTime();
        System.out.println(timediff + "ms");
    }

    /**
     * 选择排序也是一种很简单明了的排序
     * 序列分为有序与无序两部分
     * 每轮排序，从无序序列中选出最大/小的元素，交换到无序区第一个位置，并将该元素划入有序区，无序区减小
     * 经过n-1轮选择，整个序列都是有序区，排序完成
     * @param arr
     */
    public void selction(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minindex = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < arr[i]) {
                    minindex = j;
                }
            }
            if (minindex != i) {
                int tmp = arr[i];
                arr[i] = arr[minindex];
                arr[minindex] = tmp;
            }
        }
    }
}
